package scales.utils.collection.path
import scala.collection.immutable.Stack
import scala.collection.IndexedSeqLike
import scala.collection.generic.CanBuildFrom
import scales.utils._
import collection._
object PathFold {
def foldPositions[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]], ACC](locations: Iterable[Path[Item, Section, CC]], accumulator: ACC)(folder: (ACC, Path[Item, Section, CC]) => (ACC, FoldOperation[Item, Section, CC])) (implicit cbf : TreeCBF[Item, Section, CC], cm : ClassManifest[(Position[Item,Section,CC], Path[Item, Section, CC])]) : Either[(ACC, Path[Item, Section, CC]), FoldError] = {
if (locations.isEmpty) return Right(NoPaths)
val sorted = sortPositions(locations, false)
val head = sorted.head
var accum = accumulator
val rootPosition = head._1
val differentRoot = sorted.exists(p => p._1.root ne rootPosition.root)
if (differentRoot)
Right(NoSingleRoot)
else {
def withPositions( opositions : Seq[Position[Item,Section,CC]] ) : Either[(ACC, Path[Item, Section, CC]), FoldError] = {
var positions = opositions
var path = head._2
while (!positions.isEmpty) {
val (accf, res) = folder(accum, path)
accum = accf
val matched = res.perform(path)
if (matched.isLeft) {
path = matched.left.get
positions = positions.drop(1)
if (!positions.isEmpty) {
path = moveTo(path, positions.head)
}
} else return Right(matched.right.get)
}
Left((accum, rootPath(path)))
}
var positions = sorted.map(_._1).toSeq
withPositions(positions)
}
}
}
trait Paths {
def noPath[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]]
(implicit cbf : TreeCBF[Item, Section, CC]) = new Path[Item, Section, CC](Top(), Node(-1, null.asInstanceOf[ItemOrTree[Item, Section, CC]])) {
}
def rootPath[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](path: Path[Item, Section, CC]): Path[Item, Section, CC] = {
var newPath = path
while (!newPath.top.isLeft)
newPath = newPath.zipUp
newPath
}
def moveTo[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](path: Path[Item, Section, CC], newPos: Position[Item, Section, CC])
(implicit cbf : TreeCBF[Item, Section, CC]) : Path[Item, Section, CC] = {
val root = rootPath(path)
newPos.position.pop.foldLeft(root) { (path, pos) =>
Path(path, Node(pos, path.children(pos)))
}
}
type FoldR[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]] = Either[Path[Item, Section, CC], FoldError]
type PathFoldR[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]] = (Path[Item, Section, CC]) => FoldR[Item, Section, CC]
def foldPositions[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]], ACC](locations: Iterable[Path[Item, Section, CC]], accumulator: ACC)(folder: (ACC, Path[Item, Section, CC]) => (ACC, FoldOperation[Item, Section, CC])) (implicit cbf : TreeCBF[Item, Section, CC], cm : ClassManifest[(Position[Item,Section,CC], Path[Item, Section, CC])]) : Either[(ACC, Path[Item, Section, CC]), FoldError] = PathFold.foldPositions(locations, accumulator)(folder)(cbf, cm)
def foldPositions[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](locations: Iterable[Path[Item, Section, CC]])(folder: (Path[Item, Section, CC]) => FoldOperation[Item, Section, CC])(implicit cbf : TreeCBF[Item, Section, CC], cm : ClassManifest[(Position[Item,Section,CC], Path[Item, Section, CC])]) : FoldR[Item, Section, CC] =
foldPositions[Item, Section, CC, Unit](locations, ())((u, p) => ((), folder(p))).
fold(x => Left(x._2), Right(_))
val NotSameRoot = 1000
def comparePathPositions[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](path1: Position[Item, Section, CC], path2: Position[Item, Section, CC]): Int = {
if (path1 eq path2) 0
else {
if (path1.root ne path2.root) {
val p1R = System.identityHashCode(path1.root)
val p2R = System.identityHashCode(path2.root)
NotSameRoot + (if (p1R < p2R) 1 else -1)
} else
compareStack(path1.position, path2.position)
}
}
def comparePathsDirect[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](path1: Path[Item, Section, CC], path2: Path[Item, Section, CC]): Boolean =
if (path1 eq path2)
true
else
comparePathsP((path1.position, path1), (path2.position, path2))._1 == 0
def comparePaths[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](path1: Path[Item, Section, CC], path2: Path[Item, Section, CC]): (Int, Position[Item, Section, CC], Position[Item, Section, CC]) =
comparePathsP((path1.position, path1), (path2.position, path2))
def comparePathsP[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](path1: (Position[Item, Section, CC], Path[Item, Section, CC]), path2: (Position[Item, Section, CC], Path[Item, Section, CC])): (Int, Position[Item, Section, CC], Position[Item, Section, CC]) = {
if (path1._2 eq path2._2) {
val pos = path1._1
(0, pos, pos)
} else {
val (pos1, pos2) = (path1._1, path2._1)
(comparePathPositions(pos1, pos2), pos1, pos2)
}
}
def comparePathsT[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]], T](path1: (Position[Item, Section, CC], (T, Path[Item, Section, CC])), path2: (Position[Item, Section, CC], (T, Path[Item, Section, CC]))): (Int, Position[Item, Section, CC], Position[Item, Section, CC]) = {
if (path1._2._2 eq path2._2._2) {
val pos = path1._1
(0, pos, pos)
} else {
val (pos1, pos2) = (path1._1, path2._1)
(comparePathPositions(pos1, pos2), pos1, pos2)
}
}
import scalaz.Equal
import scalaz.Scalaz.equal
def toPositionalEqual[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]] : Equal[Path[Item, Section, CC]] =
equal {
comparePathsDirect(_,_)
}
def top[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](tree: Tree[Item, Section, CC])
(implicit cbf : TreeCBF[Item, Section, CC]) : Path[Item, Section, CC] =
Path(Top(), Node(0, tree))
def positionsT[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]], T](paths: Iterable[(T, Path[Item, Section, CC])]): Iterable[(Position[Item, Section, CC], (T,Path[Item, Section, CC]))] =
paths.map(x => (x._2.position, x))
def positions[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](paths: Iterable[Path[Item, Section, CC]]): Iterable[(Position[Item, Section, CC], Path[Item, Section, CC])] =
paths.map(x => (x.position, x))
def sortPositionsT[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]], T](paths: Iterable[(T,Path[Item, Section, CC])],
isDescending: Boolean = true)(implicit cm : ClassManifest[(Position[Item,Section,CC], (T, Path[Item, Section, CC]))]): Iterable[(Position[Item, Section, CC], (T, Path[Item, Section, CC]))] =
scala.util.Sorting.stableSort(positionsT(paths).toSeq, (p1: (Position[Item, Section, CC], (T,Path[Item, Section, CC])), p2: (Position[Item, Section, CC], (T,Path[Item, Section, CC]))) => {
val (res, pos1, pos2) = comparePathsT(p1, p2)
val order = (res == 1 || res == (NotSameRoot + 1))
if (isDescending) order else !order
})(cm)
def sortPositions[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](paths: Iterable[Path[Item, Section, CC]],
isDescending: Boolean = true)(implicit cm : ClassManifest[(Position[Item,Section,CC], Path[Item, Section, CC])]): Iterable[(Position[Item, Section, CC], Path[Item, Section, CC])] =
scala.util.Sorting.stableSort(positions(paths).toSeq, (p1: (Position[Item, Section, CC], Path[Item, Section, CC]), p2: (Position[Item, Section, CC], Path[Item, Section, CC])) => {
val (res, pos1, pos2) = comparePathsP(p1, p2)
val order = (res == 1 || res == (NotSameRoot + 1))
if (isDescending) order else !order
})(cm)
def sort[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](paths: Iterable[Path[Item, Section, CC]],
isDescending: Boolean = true)(implicit cm : ClassManifest[(Position[Item,Section,CC], Path[Item, Section, CC])]): Iterable[Path[Item, Section, CC]] = sortPositions(paths, isDescending).map(x => x._2)
def sortT[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]], T](paths: Iterable[(T,Path[Item, Section, CC])],
isDescending: Boolean = true)(implicit cm : ClassManifest[(Position[Item,Section,CC], (T, Path[Item, Section, CC]))]): Iterable[(T,Path[Item, Section, CC])] = sortPositionsT(paths, isDescending).map(x => x._2)
def deepestLast[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]](path : Path[Item, Section, CC]) : Path[Item, Section, CC] = {
if (path.hasChildren) {
val npath = path.lastChild.get
if (npath.isItem)
npath
else
deepestLast(npath)
} else
path
}
def preceding[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]]( path : Path[Item, Section, CC] ) : Option[Path[Item, Section, CC]] =
if (path.hasPreviousSibling) {
val t = path.previousSibling
Some(
if (t.isItem)
t
else
deepestLast(t))
} else
if (path.top.isLeft)
None
else
preceding(path.top.getRight)
def following[Item <: LeftLike[Item, Tree[Item, Section, CC]], Section, CC[X] <: IndexedSeqLike[X, CC[X]]]( path : Path[Item, Section, CC] ) : Option[Path[Item, Section, CC]] =
if (path.hasNextSibling)
Some(path.nextSibling)
else
if (path.top.isLeft)
None
else
following(path.top.getRight)
}